#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

char lookahead;
int num;
enum TERMINAL {
	ID,
	ADD,
	MUL,
	LBR,
	RBR,
	END,
	ERR
};

enum NON_TERMINAL {
	E,
	T,
	F
};

enum ACTION_TYPE {
	SHIFT,
	REDUCE,
	ERROR,
	ACC
};

#define NUM_TERMINAL  6
#define NUM_NONTERMINAL  3
#define NUM_STATES  12

struct action{
	enum ACTION_TYPE type;
	int id;
}  actionTable[NUM_STATES][NUM_TERMINAL];

int gotoTable[NUM_STATES][NUM_NONTERMINAL];

int stackPtr;
int stack[1024];
int value[1024];
void push(int state) {
	stack[stackPtr] = state;
	stackPtr++;
}

void pop() {
	stackPtr--;
}

int top() {
	return stack[stackPtr - 1];
}

void valset(int offset, int v) {
	value[stackPtr - 1 + offset] = v;
}
int valget(int offset) {
	return value[stackPtr - 1 + offset];
}

void init() {
	int i, j;

	//stack
	stackPtr = 0;
	push(0);

	//action and goto tables
	for (i = 0; i < NUM_STATES; i++) {
		for (j = 0; j < NUM_TERMINAL; j++) {
			actionTable[i][j].type = ERROR;
		}
		for (j = 0; j < NUM_NONTERMINAL; j++) {
			gotoTable[i][j] = -1;
		}
	}

	//fill in the goto table
	gotoTable[0][E] = 1;
	gotoTable[0][T] = 2;
	gotoTable[0][F] = 3;
	gotoTable[4][E] = 8;
	gotoTable[4][T] = 2;
	gotoTable[4][F] = 3;
	gotoTable[6][T] = 9;
	gotoTable[6][F] = 3;
	gotoTable[7][F] = 10;
	//fill in the action table
	actionTable[0][ID].type = SHIFT;
	actionTable[0][ID].id = 5;
	actionTable[0][LBR].type = SHIFT;
	actionTable[0][LBR].id = 4;
	actionTable[1][ADD].type = SHIFT;
	actionTable[1][ADD].id = 6;
	actionTable[1][END].type = ACC;
	actionTable[2][ADD].type = REDUCE;
	actionTable[2][ADD].id = 2;
	actionTable[2][MUL].type = SHIFT;
	actionTable[2][MUL].id = 7;
	actionTable[2][RBR].type = REDUCE;
	actionTable[2][RBR].id = 2;
	actionTable[2][END].type = REDUCE;
	actionTable[2][END].id = 2;
	actionTable[3][ADD].type = REDUCE;
	actionTable[3][ADD].id = 4;
	actionTable[3][MUL].type = REDUCE;
	actionTable[3][MUL].id = 4;
	actionTable[3][RBR].type = REDUCE;
	actionTable[3][RBR].id = 4;
	actionTable[3][END].type = REDUCE;
	actionTable[3][END].id = 4;
	actionTable[4][ID].type = SHIFT;
	actionTable[4][ID].id = 5;
	actionTable[4][LBR].type = SHIFT;
	actionTable[4][LBR].id = 4;
	actionTable[5][ADD].type = REDUCE;
	actionTable[5][ADD].id = 6;
	actionTable[5][MUL].type = REDUCE;
	actionTable[5][MUL].id = 6;
	actionTable[5][RBR].type = REDUCE;
	actionTable[5][RBR].id = 6;
	actionTable[5][END].type = REDUCE;
	actionTable[5][END].id = 6;
	actionTable[6][ID].type = SHIFT;
	actionTable[6][ID].id = 5;
	actionTable[6][LBR].type = SHIFT;
	actionTable[6][LBR].id = 4;
	actionTable[7][ID].type = SHIFT;
	actionTable[7][ID].id = 5;
	actionTable[7][LBR].type = SHIFT;
	actionTable[7][LBR].id = 4;
	actionTable[8][ADD].type = SHIFT;
	actionTable[8][ADD].id = 6;
	actionTable[8][RBR].type = SHIFT;
	actionTable[8][RBR].id = 11;
	actionTable[9][ADD].type = REDUCE;
	actionTable[9][ADD].id = 1;
	actionTable[9][MUL].type = SHIFT;
	actionTable[9][MUL].id = 7;
	actionTable[9][RBR].type = REDUCE;
	actionTable[9][RBR].id = 1;
	actionTable[9][END].type = REDUCE;
	actionTable[9][END].id = 1;
	actionTable[10][ADD].type = REDUCE;
	actionTable[10][ADD].id = 3;
	actionTable[10][MUL].type = REDUCE;
	actionTable[10][MUL].id = 3;
	actionTable[10][RBR].type = REDUCE;
	actionTable[10][RBR].id = 3;
	actionTable[10][END].type = REDUCE;
	actionTable[10][END].id = 3;
	actionTable[11][ADD].type = REDUCE;
	actionTable[11][ADD].id = 5;
	actionTable[11][MUL].type = REDUCE;
	actionTable[11][MUL].id = 5;
	actionTable[11][RBR].type = REDUCE;
	actionTable[11][RBR].id = 5;
	actionTable[11][END].type = REDUCE;
	actionTable[11][END].id = 5;
}

enum TERMINAL lexical(FILE *fp) {

	lookahead = getc(fp);

	while (lookahead == ' ' || lookahead == '\t' || lookahead == '\n') {
		lookahead = getc(fp);
	}

	if (isdigit(lookahead)) {
		num = 0;
		do {
			num = num * 10 + lookahead - '0';
			lookahead = getc(fp);
		} while (isdigit(lookahead));
		ungetc(lookahead, fp);
		return ID;
	}
	else if (lookahead == '+') {
		return ADD;
	}
	else if (lookahead == '*') {
		return MUL;
	}
	else if (lookahead == EOF) {
		return END;
	}
	else if (lookahead == '(') {
		return LBR;
	}
	else if (lookahead == ')') {
		return RBR;
	}
	else {
		return ERR;
	}
}

void parse(enum TERMINAL *input, int *number) {
	int currentState = 0;
	int currentValue = 0;
	int index = 0;
	while (1) {
		printf("currentState: %d\n", currentState);
		switch (actionTable[currentState][input[index]].type) {

		case SHIFT:
		{
					  currentValue = number[index];//store the current shifted value for further use
					  //how to shift
					  valset(0, currentValue);
					  currentState = actionTable[currentState][input[index]].id;
					  push(currentState);
					  index++;
					  break; }
		case REDUCE:
			switch (actionTable[currentState][input[index]].id) {
			case 1:
				//reduce by production 1
			{
					  currentValue = valget(-1) + valget(-3);
					  pop();
					  pop();
					  pop();
					  valset(0, currentValue);
					  currentState = gotoTable[stack[stackPtr - 1]][E];
					  push(currentState);
					  break;
			}
			case 2:
			{
					  pop();
					  currentState = gotoTable[stack[stackPtr - 1]][E];
					  push(currentState);
					  break;
			}
				//reduce by production 2
			case 3:
			{
					  currentValue = valget(-1)*valget(-3);
					  pop();
					  pop();
					  pop();
					  valset(0, currentValue);
					  //reduce by production 3
					  currentState = gotoTable[stack[stackPtr - 1]][T];
					  push(currentState);
					  break;
			}
			case 4:
			{
					  pop();
					  currentState = gotoTable[stack[stackPtr - 1]][T];
					  push(currentState);
					  //reduce by production 4
					  break;
			}
			case 5:
			{
					  currentValue = valget(-2);
					  pop();
					  pop();
					  pop();
					  valset(0, currentValue);
					  currentState = gotoTable[stack[stackPtr - 1]][F];
					  push(currentState);
					  //reduce by production 5
					  break;
			}
			case 6:
			{
					  pop();
					  currentValue = number[index];
					  currentState = gotoTable[stack[stackPtr - 1]][F];
					  push(currentState);
					  //reduce by production 6
					  break;
			}
			default:
				printf("ERROR REDUCE\n");
				exit(-1);
				break;
			}
			break;
		case ERROR:
			printf("ERROR ACTION\n");
			exit(-1);
			break;
		case ACC:
			if (input[index] == END) {
				printf("ACC\n");
				return;
			}
			else {
				printf("ERROR ACC\n");
				exit(-1);
			}
			break;
		}
	}
}


int main(int argc, char **argv) {
	enum TERMINAL input[1024];
	int number[1024];
	int inputIndex = 0;
	FILE *fp;
	enum TERMINAL temp;
	if (argc < 2) {
		printf("insufficient arguments");
		return 1;
	}
	fp = fopen(argv[1], "r");
	while ((temp = lexical(fp)) != END) {
		input[inputIndex] = temp;
		number[inputIndex] = (temp == ID ? num : -1);
		inputIndex++;
	}

	input[inputIndex] = END;
	fclose(fp);

	init();
	parse(input, number);
	printf("%d\n", valget(-1));
	return 0;
}

